#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100000;
int n,d,w[11];
int f[maxn],v[11],m;
int max(int x,int y)
{return x>y?x:y;}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d",&m,&d,&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d",&w[i],&v[i]);
			w[i]/=1000;
		}
		for(int h=1;h<=d;h++)
		{
			memset(f,0,sizeof(f));
			for( int i=1;i<=n;i++ )
				for(int j=w[i];j<=m/1000;j++)					
					f[j]=max(f[j],f[j-w[i]]+v[i]);
			m=f[m/1000]+m;
		}
		printf("%d\n",m);
	}
	return 0;
}
